package com.zwy.alhorthms;

/**
 * 归并排序
 * 将问题进行细分，先将需要排列的数组分为左右两个数组，然后在排列左边的数组和右边的数组
 * 将右边的左边的数组再分为两部分，再次进行左右两部分进行排列
 * 知道最后的数组只剩下一个数，然后将已经排列好的左右数组进行归并操作
 * @author 天火
 * @className ShellSort
 */
public class MergeSort {


    public static void main(String[] args) {

        //int[] arr = {8, 14, 2, 6, 7, 19, 1, 11, 4, 3, 10, 16, 18, 17, 20, 15, 13, 12, 5};
        int[] arr = {1, 4, 7, 8, 3, 6, 9};
        sort(arr, 0, arr.length-1);
        print(arr);

    }

    private static void sort(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if (left == right) {
            return;
        }
        //左边数组排序
        sort(arr, left, mid);
        //右边数组排序
        sort(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);

    }


    private static void print(int[] arr) {
        for (int value : arr) {
            System.out.print(value + "    ");
        }
    }

    private static void merge(int[] arr, int leftPoint, int rightPoint, int rightBound) {
        int mid = rightPoint - 1;
        //临时数组
        int[] temp = new int[rightBound - leftPoint + 1];
        //开头指针
        int i = leftPoint;
        //第二个数组的指针
        int j = rightPoint;
        int k = 0;
        while (i <= mid && j <= rightBound) {
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= rightBound) {
            temp[k++] = arr[j++];
        }
        if (temp.length >= 0) {
            System.arraycopy(temp, 0, arr, leftPoint + 0, temp.length);
        }

    }


}
